LISP
			   Vaughan R. Pratt
				M.I.T.
			      June 1977


CONTENTS

1.	Introduction to LISP
2. 	Language Design Issues in LISP
3.	The Mathematics Underlying LISP
4.	Implementation of LISP
5.	Comparison with other languages
6.	LISP - Past, Present and Future

	       1.	Introduction to LISP

	The programming language LISP was developed by John McCarthy at M.I.T.
in 1959.  The name is an acronym for LISt Processing language.  Originally LISP
was seen as supplying a list-processing capability to the Artificial
Intelligence [qv] community.  A more modern view is that LISP has two facets. 
First it is a tool whose use within AI goes far beyond the data type "list" and
whose applicability to non-AI problems is slowly becoming better appreciated. 
Second, it has been the most influential language in applying the technology of
mathematical logic to programming language design, much as APL [qv] has applied
linear algebra to programming languages.

	There is no one source of authority on what constitutes LISP, unlike
for example FORTRAN, for which an ASA (American Standards Association) standard
exists.  The major implementations are INTERLISP (formerly BBN-LISP, now
maintained chiefly at XEROX Palo Alto Research Corporation), MACLISP (M.I.T.),
and UCI-LISP (an extension of Stanford LISP developed at the University of
California at Irvine).  We present below their common features.

Data

	While it is customary to introduce a programming language by exhibiting
examples of its programs rather than its data, LISP is distinguished from other
widely used programming languages by the fact that LISP programs aλ←rλ←eλ← LISP data. 
Thus in beginning with LISP data we will also be treating some aspects of how
one writes LISP programs.  In particular, the rules for writing LISP data
(syntax) are identical to those for writing LISP programs.

Sλ←-λ←eλ←xλ←pλ←rλ←eλ←sλ←sλ←iλ←oλ←nλ←sλ←.  One might say that the basic data-type in a pocket calculator
is the real number, in that all operations are performed on reals.  The basic
data-type in LISP is the symbolic expression, or Sλ←-λ←eλ←xλ←pλ←rλ←eλ←sλ←sλ←iλ←oλ←nλ←, whose key idea
is that of the pairing function cλ←oλ←nλ←sλ←.  Just as one can define the natural
numbers (the set {0,1,2,3,...}) to be the least set containing 0 and closed
under sλ←uλ←cλ←cλ←eλ←sλ←sλ←oλ←rλ← (that is, 0 is a natural number, and adding 1 to any natural
number yields another natural number), so can one define the set of
S-expressions to be the least set containing atoms (an atom is a number or a
string) and closed under cλ←oλ←nλ←sλ←.  Just as sλ←uλ←cλ←cλ←eλ←sλ←sλ←oλ←rλ← has an inverse, namely
pλ←rλ←eλ←dλ←eλ←cλ←eλ←sλ←sλ←oλ←rλ←, with the property that pλ←rλ←eλ←dλ←eλ←cλ←eλ←sλ←sλ←oλ←rλ←(sλ←uλ←cλ←cλ←eλ←sλ←sλ←oλ←rλ←(x))=x, so does cλ←oλ←nλ←sλ←
have inverses, namely cλ←aλ←rλ← and cλ←dλ←rλ←, with the property that cλ←aλ←rλ←(cλ←oλ←nλ←sλ←(a,b))=a and
cλ←dλ←rλ←(cλ←oλ←nλ←sλ←(a,b))=b.

Lλ←iλ←sλ←tλ←sλ←.  An important use for this data type is in the representation of lλ←iλ←sλ←tλ←sλ←
such as (3 1 4 2), which is a list of four numbers.  The technique is to
represent the empty list as the atom nλ←iλ←lλ← and to represent a non-empty list as
an S-expression whose cλ←aλ←rλ← is the first element of the list and whose cλ←dλ←rλ← is the
remainder of the list.

Syntax

	Externally (i.e. on paper or on machine-readable files), S-expressions
are represented as a string of characters.  The character set used is the ASCII
set [qv] with lower case alphabetics not distinguished from upper case.

Nλ←uλ←mλ←bλ←eλ←rλ← λ←nλ←oλ←tλ←aλ←tλ←iλ←oλ←nλ←.  Numbers are written more or less as in FORTRAN [qv].  Typical
numbers are 7, 14.23, -85, .00375, 1.0E-5, the last denoting .00001.  In
general a number contains, in order, an optional minus sign, a non-empty string
of digits containing an optional decimal point, and an optional exponent. The
exponent consists of the letter E followed by an optional minus sign and a
non-empty string of digits.  Numbers are either fixed (integer) or floating
(real), the distinction being drawn by the absence or presence respectively of
a decimal point or the letter E.  A major difference between implementations is
whether numbers are interpreted as decimal or octal; however, in those
implementations using the latter (most notably the MACLISP implementation at
MIT), the user may specify any other base via a global variable called BASE,
which is set to the desired value, either a number such as 10, or the symbol
ROMAN if the user has a classical bent.

Sλ←yλ←mλ←bλ←oλ←lλ← λ←nλ←oλ←tλ←aλ←tλ←iλ←oλ←nλ←.  A symbol may be written as any sequence of printable ASCII
characters (excluding (),.'"/;) not recognizable as a number under the above
criteria for numberhood.  Thus "X", "x", "Cat", "A13", "3B", "BLOOD-PRESSURE",
"+", and "<-->" are all permissible symbols.  Characters not normally eligible
for inclusion in a symbol may be included if preceded by a slash.

Lλ←iλ←sλ←tλ← λ←nλ←oλ←tλ←aλ←tλ←iλ←oλ←nλ←.  Lists are written in parentheses, with the elements of the list
appearing in order and separated by spaces.  Thus (1 2 3), (PLUS 2 (TIMES 3
4)), (FOR WHOM THE BELL TOLLS), (1 + 2 * (3 - 4)), ((MILK (PRICE 1.49) (QTY
128)) (EGGS (PRICE .89) (QTY 12))), (PUT (BLOCK SMALL GREEN) (ON (CUBE RED
BIG))) represent five instances of lists.

Dλ←oλ←tλ←tλ←eλ←dλ←-λ←pλ←aλ←iλ←rλ← λ←nλ←oλ←tλ←aλ←tλ←iλ←oλ←nλ←.  An alternative representation is that of "dotted
pairs," in which the S-expression whose CAR is a and whose CDR is b may be
written (a . b).  Thus the list (1 2 3) could alternatively be written (1 . (2
. (3 . NIL))).  The advantage of this second notation is that it is applicable
to all S-expressions, whether or not they are lists.  The disadvantage is that
it is more cumbersome.  Thus the first notation is the preferred one for lists. 
For non-lists it is not necessary to give up the list notation altogether. 
Consider the alternative representation of (3), namely (3 . NIL).  One way to
think of the " . NIL" is as the information that the final CDR of the list is
the atom NIL.  This generalizes to longer lists in which (3 1 4 1 . NIL) is an
alternative representation of (3 1 4 1).  This in turn leads to the
generalization where the NIL can be replaced by any S-expression, e.g. (3 1 4 1
. 6).  With a little thought it becomes evident that this alternative notation
is only needed for an atomic S-expression at the end of a list.

Programs

	Certain lists have a special meaning to LISP.  For example, while
(PLUS 1 2) is indeed a list of three atoms, it is also an expression that
denotes a value, namely 3, the sum of 1 and 2.  S-expressions that can denote
values we shall call pλ←rλ←oλ←gλ←rλ←aλ←mλ←sλ←.  (This is not standard terminology; there is no
generally accepted term for this concept.)  More precisely, for an S-expression
to be a program it must either be an atom; or a list whose first element can be
interpreted as a function and whose remaining elements are programs; or a list
of the form (COND c1 c2 ... cn) where each clause ci is a list whose elements
are programs.  In the above example, (PLUS 1 2) is a program because it is a
list whose first element can be interpreted as the addition function and whose
remaining elements are atoms and hence programs.  (PLUS 1 (TIMES 2 3)) is also
a program because (TIMES 2 3) is a program.  However (1 2), though a list, is
not a LISP program because 1 cannot be interpreted as a function.  Nor is (PLUS
1 . 2), which is not even a list.

Aλ←lλ←gλ←eλ←bλ←rλ←aλ←iλ←cλ← λ←nλ←oλ←tλ←aλ←tλ←iλ←oλ←nλ←.  For programmers more familiar with 1+2*3 than (PLUS 1
(TIMES 2 3)), most implementations offer a "front-end" that permits a certain
amount of algebraic notation for LISP programs.  There is as yet no generally
agreed-upon such notation for LISP programs however, so that these front-ends
vary sufficiently widely as to constitute separate programming languages.  For
this reason we shall present all programs in this article in the S-expression
notation, which is not only relatively standard but enjoys considerable support
amongst experienced LISP programmers.

Bλ←iλ←nλ←dλ←iλ←nλ←gλ←.  All numeric atoms denote values, namely themselves.  Non-numeric
atoms may or may not denote values; when they do they are said to be bλ←oλ←uλ←nλ←dλ← to
that value, otherwise they are said to be uλ←nλ←bλ←oλ←uλ←nλ←dλ←, their default state when a
user begins an interactive session with LISP.  Binding is used to implement
both the usual notion of assignment to a variable and the assignment of
argument values to formal parameters in function definitions, processes that we
will consider later.  An eλ←nλ←vλ←iλ←rλ←oλ←nλ←mλ←eλ←nλ←tλ← is a collection of atoms together with
their bindings.

Eλ←vλ←aλ←lλ←uλ←aλ←tλ←iλ←oλ←nλ←.  LISP programs are executed by a process called eλ←vλ←aλ←lλ←uλ←aλ←tλ←iλ←oλ←nλ←, which
given a program and an environment attempts to determine what the program
denotes in that environment.  As a side effect, this process may permanently
change the environment during evaluation.  That part of LISP that cannot
permanently change the environment is sometimes called "pure" LISP, and is of
special interest in that reasoning about pure LISP programs can be done
"locally," that is, without having to consider possible unexpected interactions
between programs that do not directly call one another as functions (modulo the
remark on free occurrences of variables, in the section on LAMBDA).

LISP-defined functions

	LISP offers a number of functions.  The major ones are:

Functions on numbers:
PLUS DIFFERENCE MINUS TIMES QUOTIENT REMAINDER EXPT ABS FIX FLOAT

Predicates on numbers:
EQUAL LESSP GREATERP MINUSP ODDP NUMBERP

Functions on lists:
CONS CAR CDR APPEND LENGTH LIST REVERSE SUBST

Predicates on lists:
EQUAL EQ NULL ATOM MEMBER

Boolean functions:
NOT AND OR

Environment manipulation functions:
PUTPROP GET (or GETPROP) RPLACA RPLACD SET SETQ STORE

Control Functions:
APPLY COND EVAL FUNCTION GO LAMBDA MAP MAPC MAPCAN MAPCAR MAPCON
MAPLIST PROG QUOTE RETURN

Input-Output functions:
PRINT PRIN1 READ READCH (or READC) TERPRI

	Having introduced the commoner LISP functions and predicates,
let us explain what they are.  In doing so we shall adopt the
convention that upper case letters stand for themselves while lower
case letters denote the values of the programs that may appear
where the lower case letters appear.  For example, we shall describe
PLUS by writing "(PLUS a b) a+b", which means that the list whose car
is PLUS and whose two remaining elements are S-expressions that denote
a and b denotes the sum of a and b.

Arithmetic

(PLUS a b)	 a+b	   (TIMES a b)		axb
(DIFFERENCE a b) a-b	   (QUOTIENT a b)	a/b	
(MINUS a)	 -a	   (EXPT a b)		a␈↓#∞b␈↓#	
(ABS a)		 |a|	   (REMAINDER a b)	a mod b	(see text below)

(EQUAL a b)	 a=b	   (MINUSP a)		a<0
(LESSP a b)	 a<b	   (ODDP a)		a is odd
(GREATERP a b)	 a>b	   (ZEROP a)		a=0

	There is also a predicate (NUMBERP a) which tests whether a (which
obviously need not be numeric) is a number.

	LISP supports fixed point (integer) and floating point (real)
arithmetic.  The functions FIX and FLOAT may be applied to any numeric quantity
to coerce it to the appropriate type.  The type produced by an arithmetic
function is real when one or more of its arguments is real, otherwise it is
integer (affectionately called "contagious floating point").  This applies even
to QUOTIENT, which given two integer arguments produces the closest integer to
the answer whose absolute value does not exceed that of the answer.  (This
definition coincides with current practice in the computer world but not the
mathematical world, which omits "absolute" in that definition.)  However
REMAINDER does satisfy the identity a = qxb+r where q = (QUOTIENT a b) and r =
(REMAINDER a b).  Thus (REMAINDER -1 3) gives -1 rather than 2.

	Most implementations permit PLUS and TIMES to take any number of
arguments, with the obvious meaning in each case, and with (PLUS) (no
arguments) taken to denote 0 and (TIMES) 1.  Some implementations (e.g.
MACLISP) support multiple precision integers ("bignums"), invoking the
appropriate routines when overflow is detected so that no user intervention is
required.

Non-numeric atoms

	For reasons we will discuss later, although numeric atoms denote
themselves, non-numeric atoms do not in general.  Thus in order to denote the
atom X, it must quoted, as in (QUOTE X).  In general any S-expression may be
quoted in this way, thus (QUOTE (PLUS 1 1)) denotes, not the number 2 but a
list of three atoms.  In principle, QUOTE is only necessary for atoms since
other S-expressions can be synthesized from atoms using LIST, or CONS for
non-lists.  However, in practice the ability to quote arbitrary S-expressions
generally leads to run-time efficiency by having the S-expression constructed
once and for all when the program is read in.  It also permits the S-expression
to be written literally, making it easier to read than if it is constructed
using say LIST.  Most implementations offer a convenient abbreviation for
(QUOTE X), such as 'X or @X.

Lists

	We turn now to lists and other S-expressions.  We shall represent
m-element lists as (a1 a2 ... am), relying on the absence of any upper-case
letters in the list to distinguish it from LISP programs.

(CONS a (b1 b2 ... bn))	= (a b1 b2 ... bn).
(CAR (a1 a2 ... am))	= a1.
(CDR (a1 a2 ... am))	= (a2 a3 ... am).
(APPEND (a1 a2 ... am)
	(b1 b2 ... bn)) = (a1 a2 ... am b1 b2 ... bn).
(LENGTH (a1 a2 ... am))	= m.
(LIST a1 a2 ... am)	= (a1 a2 ... am).
(REVERSE (a1 a2 ... am))= (am ... a2 a1).
(SUBST a b c)		= c with all occurrences of b in c replaced by a.

(NULL a)		a=NIL.
(EQUAL a b)		a=b, that is a and b are either the same atom,
			or are non-atomic S-expressions with EQUAL CARs
			and CDRs.
(ATOM a)		a is an atom.

	There is also a predicate EQ which makes a concession to the internal
representation of lists; (EQ a b) holds when a and b are not merely EQUAL
element-wise but in fact are represented internally by the same data-structure. 
Testing for (EQ a b) is much faster than for (EQUAL a b), being merely a matter
of seeing whether the given pointers to a and b are the same.  (EQ a b) implies
(EQUAL a b), but not necessarily conversely.

Boolean functions:

	The atoms T and NIL serve respectively for tλ←rλ←uλ←eλ← and fλ←aλ←lλ←sλ←eλ←.  However, it
is a peculiarity of LISP that those of its functions that operate on truth
values will in fact accept any S-expression, treating NIL as fλ←aλ←lλ←sλ←eλ← and all
others as tλ←rλ←uλ←eλ←.  Though all LISP predicates, and the Boolean function NOT,
return only T or NIL, the functions AND and OR (taking arbitrarily many
arguments) return respectively their first null argument or their first
non-null argument, taking the last argument if no earlier one was satisfactory. 
If AND and OR are only given the truth values T and NIL, then this agrees with
standard usage.  However, an alternative interpretation for AND and OR is
possible in the more general case; thus (AND a b) may be interpreted as "a, AND
if so then b, otherwise NIL," while (OR a b) may be read "a, OR failing that,
then b," where NIL is considered failure.  For example, (OR (F X) 0) would
return (F X) unless the result was NIL, in which case it would return 0.

Conditional expressions

	The conditional expression "if a1 then b1 else if a2 then b2 ... else
if an then bn" is written (COND (a1 b1) (a2 b2) ... (an bn)), where (a1 b1)
denotes, not an argument whose value is a length-2 list, but a length-2 list of
S-expressions whose respective values are a1 and b1.  Thus one would write
(COND ((MINUSP a) (MINUS a)) (T a)) as an alternative to (ABS a), not (COND
(LIST (MINUSP a) (MINUS a)) (LIST T a)).  In this respect COND differs from all
other functions presented here, in that its arguments are not themselves LISP
programs but rather are lists of two programs, called cλ←lλ←aλ←uλ←sλ←eλ←sλ←.  In some
implementations each clause can have more than two elements; thus (COND (a11
a12 ... a1j) ... (an1 an2 ... ank)) would correspond to "if a11 then
(a12;a13;...;a1j) else ... else if an1 then (an2;an3;...;ank)."

Lambda expressions

	So far every expression we have been able to write has denoted either a
number or a truth value.  We have been able to use the functions already
offered by LISP, but have not been able to define functions of our own.  In
most other programming languages, defining new functions is accomplished by
some construct of the form "define f(x1,...,xn) = E(x1,...xn)" where E is some
expression referring to the functions arguments x1,...,xn.  Two things have
happened here; a function has been defined, and it has been given a name.  The
first of these does not involve any notion of machine state, as functions have
an abstract existence independent of a computer's memory, just as do numbers. 
However, the second implies that some change of state of a machine has
happened, and that in future any reference to f may be taken to be a reference
to the function now associated with f.

Cλ←hλ←uλ←rλ←cλ←hλ←'λ←sλ← λ←Lλ←aλ←mλ←bλ←dλ←aλ←.  LISP makes this distinction by permitting functions to be
defined without associating them with any particular name.  The technique for
doing this was developed by the logician Alonzo Church in the 1930's, and gave
rise to a subject that came to be known as the lambda calculus [qv].

Mλ←cλ←Cλ←aλ←rλ←tλ←hλ←yλ←'λ←sλ← λ←Lλ←Aλ←Mλ←Bλ←Dλ←Aλ←.  The general form of a lambda-expression in LISP is (LAMBDA
(X1 ... Xn) B) where X1 through Xn are symbols (non-numeric atoms) and B is a
program.  Wherever a function such as PLUS or LIST may be used, so may a
lambda-expression.  The program ((LAMBDA (X1 ... Xn) B) a1 ... an) then denotes
whatever B denotes when each Xi in B (used in B wherever a program may be used)
is bound to ai.  We say that X1 through Xn are lλ←aλ←mλ←bλ←dλ←aλ←-λ←bλ←oλ←uλ←nλ←dλ← to a1 through an
respectively.  For example, the function (LAMBDA (X) (PLUS X 3)) is a function
that adds 3 to its one argument; thus ((LAMBDA (X) (PLUS X 3)) 5) would denote
8.  On the other hand, ((LAMBDA (F) (F 3 5)) PLUS)  would not denote 8 (or
anything else), both because PLUS may not be used to denote the addition
function other than as the first element of a list that is a program (but see
FUNCTION below) and because the lambda-variable is not being used other than where
a program could be used (but see APPLY below).  (This latter usage is permitted
in the PDP10 and Multics implementations of MACLISP.)  Both of these reasons
illustrate the fact that LISP does not consider the object appearing in the
function position (i.e. as the cλ←aλ←rλ← of a program) to denote a value in the same
way that the function's arguments denote values.  This represents a major
difference between Church's lambda-calculus and LISP's use of LAMBDA.  More
recent programming languages subscribing to LISP-like ideals have followed
Church more closely in this respect and have permitted ordinary programs to
appear in the function position, giving a more satisfying and less complicated
symmetry between operator and operand.

Fλ←rλ←eλ←eλ← λ←aλ←nλ←dλ← λ←bλ←oλ←uλ←nλ←dλ← λ←oλ←cλ←cλ←uλ←rλ←rλ←eλ←nλ←cλ←eλ←sλ←sλ←.  We say that X1 through Xn oλ←cλ←cλ←uλ←rλ← bλ←oλ←uλ←nλ←dλ← in (LAMBDA
(X1 ... Xn) B).  All other non-numeric atoms in B not occurring bound in some
subexpression of B are said to oλ←cλ←cλ←uλ←rλ← fλ←rλ←eλ←eλ← in (LAMBDA (X1 ... Xn) B).

	We said earlier that pure LISP was that part of LISP which could not
cause side-effects, that is, could not permanently change the environment
(though temporary changes are possible using lambda-binding).  A claimed
benefit was the lack of unexpected interaction between remote programs, due to
one program changing the value of an atom used by another program.  According
to our definition of environment, remote interaction is still possible via the
lambda-binding in one function of a variable used in another function called
(possibly very indirectly) by the first function.  The environment in which the
lambda-binding was done may still have that binding when the called function is
evaluated, which may or may not have been what the user intended; it is
difficult to keep track of all uses of a given variable throughout a large
program.  Thus a more complete definition of pure LISP would forbid variables
occurring free in lambda-expressions.

Rλ←eλ←cλ←uλ←rλ←sλ←iλ←vλ←eλ← λ←Lλ←Aλ←Mλ←Bλ←Dλ←Aλ←.  It is possible for a function defined using LAMBDA to refer
to itself, thus permitting recursive definitions, with the help of the LABEL
construct, which like LAMBDA is not a function but rather a way of constructing
functions.  If L is a lambda expression wishing to refer to itself as the atom
F, it may do so by being written (LABEL F L).  As a simple example, we may
multiply the numbers 23 and 37 using only the arithmetic function PLUS and the
predicate ZEROP, with

((LABEL M (LAMBDA (X Y) (COND ((ZEROP X) 0)
			      (T (PLUS Y (M (PLUS X -1) Y)))))) 23 37)

	This recursive definition of M as multiplication relies on the two
facts 0xX = 0 and Y+(X-1)xY = XxY.  Note that M is lλ←oλ←cλ←aλ←lλ← to this expression,
just as are the lambda-variables X and Y; the use of this expression has no
bearing on the meaning of M in other expressions.

Functions as data

	We have so far seen functions appearing only in the function position
of LISP programs.  However, functions can also be treated as values; the
S-expression (FUNCTION F) denotes whatever function F can be interpreted as,
where F is any S-expression that can appear in the function position of a
program.  Thus (FUNCTION PLUS) can appear as an argument of some other
function, as can (FUNCTION (LAMBDA args body)).

	The function APPLY permits functions that exist in this form to be
applied to a list of its arguments.  Thus if F were to denote the function
PLUS, then (APPLY F (LIST 1 2)) would denote the same thing as (PLUS 1 2). 
Since (FUNCTION PLUS) denotes the addition function,
(APPLY (FUNCTION PLUS) (LIST 1 2)) also denotes the same thing, as does
((LAMBDA (F) (APPLY F (LIST 1 2))) (FUNCTION PLUS)).

	A novel application of APPLY is to form the sum of the elements of the
list x, using (APPLY (FUNCTION PLUS) x).  For if x were (3 5 9) then this would
be just as though we had written (PLUS 3 5 9).  Likewise we can compute the
product of the elements of a list, using (FUNCTION TIMES).  If we want to tell
whether a list does not contain NIL, an alternative to (NOT (MEMBER NIL x)) is
(APPLY (FUNCTION AND) x).  (FUNCTION OR) will permit testing for any non-NIL
element, and will return the first one if there is one.  Some implementations
have MAX, MIN, GCD and other associative functions that may take arbitrarily
many arguments, and the same technique may be applied.  For example, (APPLY
(FUNCTION MAX) x) will return the largest number in the list x.  When LESSP is
implemented so that the meaning of (LESSP a1 a2 ... an) is a1<a2<...<an, then
(APPLY (FUNCTION LESSP) x) tests whether x is an ordered list of distinct
numbers.

	Another use of functions as data has to do with the function MAPCAR,
which takes as its first argument a function (of n arguments) and as its
remaining n arguments (the same number n) lists of values to apply the function
to, returning the results in the form of a list.  For example, suppose a is the
list (1 2 3).  Then (MAPCAR (FUNCTION MINUS) a)  denotes the list (-1 -2 -3). 
The negation function was applied to each element in turn on the list, and the
resulting values were formed into a list of the same length as a. If in
addition b were the list (4 5 6), then (MAPCAR (FUNCTION PLUS) a b) would
denote the list (5 7 9), just as though the lists were being added together as
vectors.  In full generality, (MAPCAR f (x11 x12 ... x1n) (x21 x22 ... x2n) ...
(xm1 xm2 ... xmn)) would denote the list (f(x11,x21,...,xm1) f(x12,x22,...,xm2)
... f(x1n,x2n,...,xmn)).  (Readers familiar with matrix algebra may visualize
the m lists as the m rows of an mxn matrix.  Then f is applied to each of
the n columns to yield a list of n items.)

	One way to think of MAPCAR comes from thinking of lists as functions
from numbers to list elements, where the number indexes into the list.  Thus
the list (3 1 4 1) may be considered to be the function that maps 1 to 3, 2 to
1, 3 to 4 and 4 to 1.  (This is not to say that LISP will let you apply lists
as though they were functions.)  Then (MAPCAR f x) forms the composition of f
with x.

	A conceptual use for this way of thinking about MAPCAR is as follows. 
To apply two functions, say f and g, in turn to each element of x, to yield
(f(g(x1)) f(g(x2)) ... f(g(xn))), one way is to form the composition of f and g
using (MAPCAR (FUNCTION (LAMBDA (Z) (APPLY f (LIST (APPLY g (LIST Z)))))) x),
or (MAPCAR (FUNCTION (LAMBDA (Z) (F (G Z)))) x) if we have S-expressions F and
G that may be interpreted as f and g.  However, noting that composition is
associative, we may see with no further thought that we may also write it as
(MAPCAR f (MAPCAR g x)).

	Combining MAPCAR with APPLY can lead to some powerful constructs.  For
example, to test whether the list x contains a negative number, use (APPLY
(FUNCTION OR) (MAPCAR (FUNCTION MINUSP) x)).  To transpose a matrix m
represented as a list of lists, use (APPLY (FUNCTION MAPCAR) (CONS (FUNCTION
LIST) m)).  (This approaches the obscurity of similarly "clever" APL
programming!  We do not necessarily recommend this as a programming style.  The
point is that these operations are very powerful; whether such uses are
considered abuses is a human engineering issue.)

Environment manipulation functions:

	Everything we have discussed so far has not required the
notion of a machine state or of a computer memory.  As a consequence
we have been able to talk in terms of S-expressions simply denoting
values without having to talk about events or time.  We come now to a
class of functions where we must say "before" and "after" in order to
specify their meaning.


----MORE TO COME LATER-----

PUTPROP GET (or GETPROP) RPLACA RPLACD SET SETQ STORE

Control Functions:
EVAL GO MAP MAPC MAPCAN MAPCAR MAPCON
MAPLIST PROG QUOTE RETURN

Input-Output functions:
PRINT READ READCH (or READC) TERPRI

2. 	Language Design Issues in LISP

-----?????-----

	3.	The Mathematics Underlying LISP

	LISP borrows more heavily than any previous language from the
elegant yet powerful concepts that had evolved in the world of mathematical
logic in the last hundred years.  These concepts included:

	Abstract objects
	The pairing function as a universal data constructor
	Functions defined by lambda-abstraction
	Recursively defined functions

Aλ←bλ←sλ←tλ←rλ←aλ←cλ←tλ← λ←oλ←bλ←jλ←eλ←cλ←tλ←sλ←.  The concept of an abstract object is at least as old as the
concept of a number divorced from its representation.  Essentially all
high level programming languages embody the notion of abstract
numbers, whether or not they attempt to hide the representation by
forbidding representation-dependent operations (e.g. shifts and
Boolean operations on a binary machine).  They do this by allowing the
programmer to forget about the representation of the number if he
chooses and to imagine that he is manipulating only the abstractions. 
The test for whether complete liberation from the representation has
been attained is whether the object in question can be passed around
inside the computer in all possible ways.  An abstract object can:

 1.  be assigned to some variable;
 2.  be passed as an actual parameter of some procedure or function;
 3.  be returned as the value of some function.

	For example, in ALGOL, integers, reals and Booleans satisfy
all three tests and so are truly abstract objects.  (To judge from the
programming styles apparent in the early years of CACM's algorithms
department, the idea of Booleans as abstract objects was clearly a
difficult thing for people to come to grips with, and many programmers
continued to use two numbers, 0 and 1 usually, even though it was clear
that a Boolean was the appropriate data type.)  On the other hand, ALGOL
arrays fail tests 1 and 3, as do functions.  This restriction on arrays and
functions forced a clumsy programming style in ALGOL, as in most high level
programming languages of ALGOL's day; for example, the programmer could not
define a function that took as arguments two matrices and returned as value
their product.  Instead he had to write a procedure that took as arguments
three matrices, and arrange for the procedure to store the product of the
first two arguments into the third.  To accomplish this required a further
complication involving the distinction between parameters called-by-value
and parameters called-by-name, so that the programmer had to have the third
argument called-by-name.  (To add insult to injury, in most implementations
he also had to call the first two arguments by name to avoid pointless
inefficiency in making copies of the arrays, a problem caused by the
difficulty of the compiler's telling whether a copy is necessary.)

	These tests were not spelled out until as late as 1968 [1] in
connection with the programming language POP-2 developed by R.
Popplestone at the University of Edinburgh.  Popplestone applied these
three criteria together with a fourth (that objects always be testable for
equality) to identify what he called "first-class citizens" for which the
four tests constituted their "bill of rights."  (For the fourth test
Popplestone got around the problem of testing equality of complicated
objects like functions and circular lists by changing the usual notion of
equality to that of LISP's EQ predicate.  This is inconsistent with the
standard notion of equality of two abstract objects, for which no effective
implementation is possible in general for functions, and we have therefore
omitted Popplestone's fourth test.)  It is clear in hindsight that even
though these conditions had not been made explicit at the time LISP was
conceived, the initial version of LISP met them for many more of its data
types than had any previous language.

Pλ←aλ←iλ←rλ←iλ←nλ←gλ←.  The power of the pairing function (LISP's CONS) was recognized in
mathematics half a century before LISP was developed.  In this section we
shall write (CONS a b) as a.b, in the mathematical spirit of concise
notation for ubiquitous concepts.  In the introduction we simply postulated
CAR and CDR without further ado; however, if we wished to be truly
mathematically pedantic, we might more properly begin by observing the
basic property of CONS, that if a.b = c.d then a=c and b=d.  That is, a.b
is an object from which in principle a and b can be reconstructed. 
Contrast this with +, where a+b = c+d does not necessarily imply either a=c
or b=d, whence given the number 4+5 (i.e. 9) it is not possible to say for
certain whether this was arrived at as the sum of 4 and 5, 3 and 6 or any
other combination.  The importance of this "information-preserving"
property of CONS is that it leads to abstract objects that can function as
memories holding two independent objects.  The apparent limitation to two
objects disappears when it is realized that if a.(b.c) = d.(e.f) then a=d
and b.c=e.f, whence b=e and c=f.  So by using CONS twice we can construct a
three-memory object.  Continuing in this way we can in principle build
indefinitely large memories as abstract objects.  This of course is all
obvious without this pedantry, but it is of interest to note that we were
able to say this much about CONS without having to mention the "memory
accessing" functions CAR and CDR, which in this section, continuing in our
spirit of brevity, we may write as α and β, which of course satisfy α(a.b)
= a and β(a.b) = b.  

	An important application of CONS is in the construction of lists, a
data type that is "synthetic" in LISP in the sense that it is not given as
primitive but is defined using CONS.  An object called NIL is assumed
given, and is taken to denote the empty list.  Then a.NIL is taken to be a
list of length 1 whose only element is a.  The object a.(b.NIL) is a list
of length 2, with elements a and b, and so on.  In general, if L is a list
so is a.L, and a.L has length one more than that of L.  The decision to
begin with NIL as the CDR rather than as the CAR and to form a.L rather
than L.a is mainly a matter of convenience in the external representation
of lists in LISP, where a.(b.NIL) is written as (a b).

\λ←-λ←aλ←bλ←sλ←tλ←rλ←aλ←cλ←tλ←iλ←oλ←nλ←.  In 1936 A. Church introduced the notion of \-defined
functions.  The idea is that, while one might intuitively speak of "x/2" as
denoting a function of x, it seems to lack the property one expects of a
function that it can be applied to an object.  To deal with this, Church
introduced the terminology "\x.M", where if M is a function of x (in the
sloppy usage) then "\x.M" is a function (no longer of x particularly) in
the strict sense, just as "cos" and "log" are functions in the strict sense
and are not associated with any particular variable.  "\x" is considered as
a meta-operator called lambda-abstraction whose job is to abstract the "of
x" from "function of x."  Thus "x+1" denotes a function of x while "\x.x+1"
denotes just a function (the successor function).  Moreover, "\x.x+1"
denotes the same function as "\y.y+1", illustrating that lambda-abstraction
removes the significance of the choice of variable.  Similarly "\x.f(g(x))"
denotes the composition of f and g, "\x.1" denotes the constant function
that returns 1 no matter what it is applied to, "\x.x*x*x" denotes the
cubing function, and so on.  Moreover, the arguments could themselves be
functions, allowing the creation of functionals (functions of functions),
for example "\f.(\x.f(f(x)))" which denotes the functional which, given a
function "f" returns a function corresponding to applying "f" twice.

	McCarthy adapted Church's \-notation to LISP, generalizing it to
several variables.  This gave the programmer the power to create, as
abstract objects, new functions from old, just as in Church's system. 
Unfortunately, nested lambda-abstractions, as in the "twice" example above,
were not catered for, losing much of the power of Church's version.

Rλ←eλ←cλ←uλ←rλ←sλ←iλ←vλ←eλ←lλ←yλ← λ←dλ←eλ←fλ←iλ←nλ←eλ←dλ← λ←fλ←uλ←nλ←cλ←tλ←iλ←oλ←nλ←sλ←.  The story is often told (in one form or
another) of the mathematician who was asked "How do you boil an egg?"  He
replied, "Get a pan, fill it with water, place the water on the stove,
light the stove, wait till the water bubbles, put the egg in, wait three
minutes, then remove the egg."  Then he was asked "How do you boil water?"
to which he replied, "Get an egg, reducing it to the previous problem."  If
nothing else there is a compelling clarity of thought expressed in that
solution, and mathematicians have used the idea of reducing one problem to
another in many situations, particularly in definitions where one thing is
defined in terms of another.  In its most powerful form, an object may be
defined in terms of itself, or rλ←eλ←cλ←uλ←rλ←sλ←iλ←vλ←eλ←lλ←yλ←, which may lead to a whole
series of reductions as the definition gets used over and over again.  If
the definition is worded sufficiently carefully these reductions will not
continue for ever but will tλ←eλ←rλ←mλ←iλ←nλ←aλ←tλ←eλ←.  If you look up the definition of
"five" in some dictionaries you will be told that it is one larger than
four, requiring you to go back into the dictionary if you don't know what
"four" is.  Eventually you will reach zero, where you will find a
definition not requiring you to look up yet another number.  Had the
definition of "five" been "one less than six" it would have been a
different story.

-----DO THE FOLLOWING PARAGRAP	A slightly less trivial example is the definition of addition of
natural numbers (non-negative integers) using only the successor function
s = \x.x+1.  Suppose we have defined x+y for all values of x less than 5 and
for all values of y.  Then we may define 5+y to be the successor of 4+y,
which we know has been defined.  More generally, if we know what x+y is
then we know what s(x)+y is, namely s(x+y).  The only case left open then
is 0+y, which we can define to be y.  We can thus write as our formal
definition of +,

		   0+y = y
		s(x)+y = s(x+y),

where the equations are considered to hold for all numbers x and y, i.e. x
and y are uλ←nλ←iλ←vλ←eλ←rλ←sλ←aλ←lλ←lλ←yλ← qλ←uλ←aλ←nλ←tλ←iλ←fλ←iλ←eλ←dλ←.  Now to determine 3+7, we observe that 3
is s(2) and s(2)+7 is s(2+7) by the second equation.  But now we need to
reuse the definition of "+" to determine 2+7, and this continues until we
reach 0+7, by which time our expression has grown to s(s(s(0+7))).  At the
next step we get s(s(s(7))), and then s(s(8)), s(9), and finally 10.  The
recursion terminated at last!  It is easy to see that the recursion will
terminate for all starting values of x and y that are non-negative (the
only values we wanted to look at in this example).

	For a computer to use this definition, a modicum of intelligence is
needed to decide which equation is applicable, and how it is to be applied. 
We can specify more exactly what to do to calculate x+y if we use the
conditional "if a then b else c" defined as (if true then b else c) = b
and (if false then b else c) = c, and the predecessor function p defined
as p(s(x)) = x.  Then we may write

	x+y = if x=0 then y else s(p(x)+y).

Again the free variables x and y are assumed to be universally quantified.
The important property of this new definition is that it supplies a single
universally applicable definition of "+", universal in the sense that all
questions involving "+" appear in the form "x+y".  Thus to eλ←vλ←aλ←lλ←uλ←aλ←tλ←eλ← 3+7, we
can simply apply every definition we have to everything possible until we
have eliminated "+":

	3+7 = if 3=0 then 7 else s(p(3)+7)
	    = if false then 7 else s(if 2=0 then 7 else s(p(2)+7))
	    = s(if false then 7 else s(if 1=0 then 7 else s(p(1)+7)))
	    = s(s(if false then 7 else s(if 0=0 then 7 else s(p(0)+7))))
	    = s(s(s(if true then 7 else s(if p(0)=0 then 7 else s(p(p(0))+7)))))
	    = s(s(s(7)))
	    = s(s(8))
	    = s(9)
	    = 10

	As can be seen, what we did was decided for us entirely by the rule "apply
every definition possible at each step."  Going from the first line to the
second, three definitions applied.  Four applied at each of the next two
steps, then three at the next (we had no definition for p(0)), then one at
each of the next four steps.

	The rule we used to apply definitions is certainly simple-minded,
but it seems to be wasteful of time and space.  In particular, we spend
effort producing s(if p(0)=0 then 7 else s(p(p(0))+7)) only to discard it
at the end.  To save time, a more sensible strategy would be to evaluate
only the first argument of the "if" to determine which of the other two
arguments to discard.  Also, we need not apply the definition for + until
we have finished evaluating its arguments, since they had better evaluate
to numbers and this representation of the arguments of + is the most
compact.  This leads to:

	3+7 = if 3=0 then 7 else s(p(3)+7)
	    = if false then 7 else s(p(3)+7)
	    = s(p(3)+7)
	    = s(2+7)
	    = s(if 2=0 then 7 else s(p(2)+7))
	    = s(if false then 7 else s(p(2)+7))
	    = s(p(3)+7)
	    = s(s(1+7))
	    = s(s(if 1=0 then 7 else s(p(1)+7)))
	    = s(s(if false then 7 else s(p(1)+7)))
	    = s(s(s(p(1)+7)))
	    = s(s(s(0+7)))
	    = s(s(s(7)))
	    = s(s(8))
	    = s(9)
	    = 10

-----IF GOD INVENTED THE NATURAL NUMBERS AND MAN THE REALS, WHO THE HELL
WAS RESPONSIBLE FOR COMPUTATION SEQUENCES?
(Yes, I know that's not quite how Kronecker put it.)-----

-----MORE TO COME-----

	4.	Implementation

	The degree of difficulty of implementing a programming language
depends largely on the extent of the difference between the implemented
language and the implementation language.  We shall begin with a very
abstract notion of an implementation language, consisting simply of some
carefully chosen mathematical functions, and later consider more
down-to-earth machine languages.

	Let us assume that we are given the domain of S-expressions, along
with certain functions and predicates on that domain.  Some of those
functions (whose LISP names are PLUS, TIMES, etc) are the sort of function
that a computer's machine language might already provide.  The functions
CONS, CAR and CDR, and the predicates EQUAL, ATOM and NULL, are functions
whose implementation we will consider later.  (While they are not generally
provided for in present-day machine languages, one can at least conceive of
this happening in the future.)  We will assume that each atom F that may
legitimately appear in the function position of an S-expression is
associated with some such function or predicate f whose implementation has
been taken care of one way or another.  We also assume that we have
environments; an environment is a function from variables (i.e. symbols,
non-numeric atoms) to S-expressions, together with a mechanism for
producing new environments from old, namely [X:=a]e, which denotes the
environment that differs from e only in that the value of the variable X is
a rather than e(X).  Finally we have the function eλ←vλ←aλ←lλ←, which
given an S-expression together with an environment e returns the value
denoted by that S-expression in that environment.  We require eλ←vλ←aλ←lλ← to
satisfy the following equations.  (We shall use upper case letters to
denote S-expressions, lower case to denote all other objects.)

 eval(N,e)	=   N		where N is a number
 eval(V,e)	=   e(V)	where V is a variable
 eval((F A1 ... An),e)		where F is a symbol with function f
		=   f(eval(A1,e),...,eval(An,e))
 eval(((LAMBDA (X1 ... Xn) B) A1 ... An),e)
		=   eval(B,[X1=eval(A1,e)]...[Xn=eval(An,e)]e)
 eval((COND (A1 B1) ... (An Bn)), e)
		=   eval(Bi,e) where i is the least such that
				eval(Ai,e) is non-null

	This definition is the "no-side-effects" definition.  It is
appropriate for that subset of LISP that excludes PUTPROP, SETQ, RPLACA and
RPLACD.

-----THERE IS MORE-----

	5.	Comparison with other languages

T

	6.	LISP - Past, Present and Future

	The peculiar names of the accessing functions refer to the two
fields in a word of the IBM 704, the host for the original implementation
of LISP.  These fields were the Contents of Address Register (CAR) and
Contents of Decrement Register (CDR).

-----ETC-----

-----THINGS TO MENTION SOMEWHERE-----

Organization of LISP programs

	Complex LISP programs are generally decomposed into a series
of function definitions which may either be typed directly to LISP or
entered off-line (usually via the computer's file system and editing
program) and loaded into LISP.  Once loaded, a program is invoked by
the user's calling one of the functions.

	This section discusses the data types available in LISP.   The
following may not be found all together in any one implementation of LISP,
but most implement

-----

	numbers		integers (unlimited size), reals
	bit vectors	various applications, e.g. PASCAL's sets
	booleans	T and NIL (for false)
	atoms		serving double duty as strings and variables
	lists		for which LISP is best known
	property lists	various applications, e.g. PASCAL's records
	arrays		unrestricted as to type or dimension
	function(al)s	using LAMBDA and APPLY
	programs	using EVAL and QUOTE

-----

Use of property lists to implement cases - for both interpreter & user
Idea of doing all hashing when you read in the data
Interpreter vs compiler

------
FONT 31VR, S30GRK, 31VRI
VSP 6 FSP 31 PAG 1 ULS ␈↓α ULE ␈↓
MAP \:␈λ
TECOXCT 79FSADLINE⎇W :↑I⎇EXIT⎇/70FSADLINE⎇/